In asymmetric cryptography, secret large prime numbers are needed. In many cryptographic applications, prime numbers should be random. Conventionally, generating random prime numbers is a process that requires significant resources in terms of processing power and time. Typically, time can be saved by increasing the processing power applied to the task of generating the random prime number. Where both time and processing power are scarce, a solution may be to predetermine the random prime number under circumstances where time and processing power are less scarce and store the predetermined random prime number for later use. The storing of the random prime number for later use, however, adds to a risk of compromising the security of the random prime number.
A typical cryptographic application is Rivest Shamir Adleman (RSA) cryptography. RSA requires two secret randomly selected or generated prime numbers P and Q. Herein, randomly selected or generated refers to a level of entropy of the number that, in the randomly selected or generated number, is sufficient for the purpose why the number was selected or generated in the first place. In the conventional method the two secret prime numbers P and Q are multiplied to form a public module N=P*Q. A pair of keys, i.e., a private or secret key D plus a public key E, is then given by the condition of E*D=1 mod phi(N), wherein phi(N)=(P−1)*(Q−1) is Euler's totient function that counts the totatives of N, i.e., the positive integers less than or equal to N that are relatively prime to N. In a typical cryptographic application, first a suitable public key E is selected and then private key D is calculated by inversion of E mod phi(N). Thus, D=E^−1 mod (P−1)*(Q−1).
Security of RSA cryptography rests on the difficulty of factorization of the public parameter N. Having accomplished the factorization, an attacker can then calculate Euler's function phi(N) and, using D=E^−1 mod phi(N), obtain private key D from public key E. Having private key D, the attacker can do whatever the rightful owner of private key D is able to do. RSA is secure to the extent that, at least for large N, calculation of secret prime factors P and Q is difficult. Accordingly, an attacker should be prevented from obtaining P and/or Q.
Given that factorization is difficult only for large N, in order to ensure security, primes P and Q need to have a minimum size that, however, isn't fixed but increases over time in step with technological advance and increasing processing power available to an attacker. Presently, for P and Q to be secure, these numbers should be larger than 2^1024. Further, P and Q need to be random and have a certain level of entropy, i.e., a certain level of uncertainty and unpredictability, such that an attacker cannot guess the numbers. Presently, for P and Q to be secure, these numbers should have an entropy of at least 100 bit. In other words, a random number generator used in a method to generate P and Q should be able to generate at least 2^100 different prime numbers. Thus, an attacker who is not able to perform a factorization of N, should on average test 2^99 prime numbers in order to find P and/or Q. To give one example, if P did merely have an entropy of 32 bit, then an attacker could generate a set of all 2^32 prime numbers and test, if any candidate prime number C in the set divides public value N. Having thus identified C|N, P and Q would be found as P=C and Q=N/C.
Conventional methods to generate secret prime numbers, at a step 1, generate a random candidate number C, at a step 2, test candidate number C to determine, if candidate number C is prime, and, at a step 3, if C is not prime, go on to generate another candidate number C′, test that candidate number C=C′, and so forth, until C is found to be prime, in which case C, at a step 4, is output as prime number P. Random candidate number C can be generated using a true random number generator (TRNG) or a pseudo random number generator (PRNG), wherein the PRNG is a state machine holding a state with a certain bit length that derives, from the state, both the pseudo random number and an updated state to hold for further use. Typically, at the beginning of operation, the PRNG is set to an initial state that is based on a random secret, called “seed”. Any subsequently generated pseudo random number depends deterministically on the seed. The level of entropy of any subsequently generated pseudo random number is upper-limited to the level of entropy of the seed. Some generators operate as hybrids of TRNG and PRNG.
A typical test for primality of a candidate number, for example, the Pocklington-Lehmer test, can be used. The Pocklington-Lehmer test uses auxiliary parameters such as pre-generated small prime numbers. The small prime numbers can add to the entropy of the generated candidate number. Other typical tests for primality of a candidate number are probabilistic tests that determine so-called pseudo prime numbers. Examples of probabilistic tests are Fermat test, Solovay-Strassen test, and Miller-Rabin test. Probabilistic tests can differentiate between a number being a prime number and the number being composed, i.e., non-prime, wherein the test result may be subject to some statistical error. Statistical error can provide a result where a composed number is found to be prime even though the number is actually non-prime. Today, applications can provide for an error probability less than one in 2^100 and thus be negligible. Therefore, herein reference is made collectively merely to the term “prime numbers”. Primality tests can be combined. For example, a small prime divisability test can precede a Miller-Rabin test. Performing the small prime divisability test takes little time and thus brings about efficiencies. For example, using the smallest 54 prime numbers to perform the small prime divisibility test on the candidate number can reduce by up to 90% the number of Miller-Rabin tests that need to be performed. In the afore-described conventional method to generate prime numbers, upon performing the conditional jump from step 3 to step 1, a subsequent candidate number does not necessarily need to be generated all anew, but can be derived from an existing candidate number C. Typical methods to generate the first candidate number C encompass: selecting C=true random number; using a seed as an input to a pseudo random number generating function to provide C=pseudo random number. The pseudo random number can be C=f(seed), or an existing random number rand=f(seed) can be used as an input to a generating function to provide C:=g(rand). In some applications the function f can have cryptographic properties. For example, f can be a hash function. In another example, f is a block cipher such as defined in the Advanced Encryption Standard (AES). Subsequent candidates C can be generated in several ways. A typical method is to derive a subsequent candidate number from a previous candidate number, C:=g(C), for example by incrementation, C:=C+D, wherein D denotes an increment step value, by hashing, C:=hash(C), by adding a random number C:=C+R, wherein R denotes a random value, by combination of these, C:=hash(C+R), and others. Subsequent candidates can also be derived by not depending on one another, C=f(S, i), wherein S denotes a seed value and i denotes, e.g., a counter value. The counter value can be an independent parameter such as several random numbers generated earlier.
Generating prime numbers, for at least two reasons, takes a lot of time: Firstly, according to the prime number theorem, probability of a random number to be prime is approximately 1/(n*ln(n)), wherein n denotes the number of bits used in representing the random number, herein also referred to as bit length. To give an example, probability of a random number having a representation of bit length n=1024 to be prime is approximately 1/710, meaning that in order to determine a prime number, on average, the primality test needs to be performed on 710 random numbers. Secondly, given a candidate number of bit length n, the primality test typically requires at least one exponentiation of (almost) n bit length. For example, when applying the Fermat test on the candidate number C, a random or predetermined number a is exponentiated according to the expression a^(C−1) mod C. Even when using the small prime divisibility test before applying another one of the above mentioned primality tests, still the other primality test needs to be performed 71 times on average. In contrast, generating a random candidate number, in typical applications, is fast.
One concern in cryptographic systems is side channel attacks, i.e., attacks based on information gained from the physical implementation of a cryptosystem. For example, timing information, differential power consumption, electromagnetic leaks or even sound can provide an extra source of information which can be exploited to break the system. In key generation for RSA cryptography, however, side channel attacks are less of a concern than in other applications, since side channel attacks require repeated use of the secret in a cryptographic algorithm, in order to enable the attacker to break the secret. A typical side channel attack may require information on the result of performing the algorithm. In the case of secret key generation, however, the result is the secret key, and therefore not readily available to the attacker who, at any rate, typically has but one performance of the algorithm to observe information in the side channel. The scarcity of information in the side channel makes the generation of secret keys rather resilient to side channel attacks.
In some applications a cryptosystem may provide little permanent memory such as non-volatile memory relative a number of secret keys to be kept by the cryptosystem. For example, embedded systems such as typically used in a chipcard or in a trusted platform module (TPM, which is a specification for a secure cryptoprocessor written by a computer industry consortium called the Trusted Computing Group (TCG)) have rather limited resources at their disposal. In this situation it is a good solution to use a deterministic prime number generation, i.e., one that only depends on a secret seed value, and re-generate the prime number when it is needed. In this case, instead of storing a long bit representation of prime P, it suffices to store the seed whose bit length can be limited to the bit length of the entropy required in the random prime number(s) for use in the implementation. For example, where a random prime number whose representation has a bit length of 1024 bit is required to have entropy of 100 bit, savings in memory of above 90% can realised by storing the seed instead of the random prime number.
In some implementations time to regenerate the random prime number can be a concern. In particular, in RSA, time used for number regeneration can matter, since two prime numbers P and Q need to be regenerated. Therefore, there is a need to accelerate regeneration of prime numbers.
In some implementations side channel attacks can be a concern. Given that a same prime number is generated more than once, an attacker, for example, by repeatedly running a regeneration process may create opportunities to observe information in the side channel that eventually is sufficient to break the secret and determine the secret prime number. Side channel attacks can be a particular concern in primality tests where exponentiation is performed using the candidate number C such as, for example, the Fermat test that performs a^(C−1) mod C. Typically, the exponentiation is performed by applying a square and multiply algorithm whose steps closely correlate with the candidate number C submitted to the test, and that enable an attacker to break the secret bit by bit.